Results: Plots and Tables

This report contains different plots and tables that may be relevant for analysing the results. Observe:

• The hypercube \(Y_N\) is placed in, is approx. \([0, 10000m]^p\), since for each subproblem \(Y_N^s \subset [0, 10000]^p\). That is, more subproblems create a larger hypercube for the master problem and the volume (number of integer points) grows exponentially in \(p\).
• Given \(|Y_N|\), we can find the hypercube as \[[l_1, u_1] \times \cdots \times [l_p, u_p],\] where \(l_i = \min_{y \in Y_N}(y_i)\) and \(u_i = \max_{y \in Y_N}(y_i)\).
• The number of integer points in the hypercube is \[\prod_{i = 1}^p (u_i - l_i + 1)\]

Statistics for alg1

Given a problem consisting of \(m\) subproblems with \(Y_N^s\) given for each subproblem \(s\), we use a filtering algorithm to find \(Y_N\) (alg1).

The following instance/problem groups are generated given:

• \(p=2,\ldots, 5\). [4 options]
• \(m=2,\ldots 5\) where \(m\) is the number of subproblems. [4 options]
• All subproblems have the same method config or half have method u and l. [4 options]
• Five instances for each config. [5 options]

Status

1142/1280 problems have been solved, i.e. 138 remaining:

##   [1] "alg1-prob-2-100|100|100|100|100-lllll-5_1.json"
##   [2] "alg1-prob-2-100|100|100|100|100-lllll-5_2.json"
##   [3] "alg1-prob-2-100|100|100|100|100-lllll-5_3.json"
##   [4] "alg1-prob-2-100|100|100|100|100-lllll-5_4.json"
##   [5] "alg1-prob-2-100|100|100|100|100-lllll-5_5.json"
##   [6] "alg1-prob-2-200|200|200|200|200-lllll-5_1.json"
##   [7] "alg1-prob-2-200|200|200|200|200-lllll-5_2.json"
##   [8] "alg1-prob-2-200|200|200|200|200-lllll-5_3.json"
##   [9] "alg1-prob-2-200|200|200|200|200-lllll-5_4.json"
##  [10] "alg1-prob-2-200|200|200|200|200-lllll-5_5.json"
##  [11] "alg1-prob-2-300|300|300|300|300-lllll-5_1.json"
##  [12] "alg1-prob-2-300|300|300|300|300-lllll-5_2.json"
##  [13] "alg1-prob-2-300|300|300|300|300-lllll-5_3.json"
##  [14] "alg1-prob-2-300|300|300|300|300-lllll-5_4.json"
##  [15] "alg1-prob-2-300|300|300|300|300-lllll-5_5.json"
##  [16] "alg1-prob-2-50|50|50|50|50-lllll-5_1.json"     
##  [17] "alg1-prob-2-50|50|50|50|50-lllll-5_2.json"     
##  [18] "alg1-prob-2-50|50|50|50|50-lllll-5_3.json"     
##  [19] "alg1-prob-2-50|50|50|50|50-lllll-5_4.json"     
##  [20] "alg1-prob-2-50|50|50|50|50-lllll-5_5.json"     
##  [21] "alg1-prob-3-100|100|100|100|100-lllll-5_1.json"
##  [22] "alg1-prob-3-100|100|100|100|100-lllll-5_2.json"
##  [23] "alg1-prob-3-100|100|100|100|100-lllll-5_3.json"
##  [24] "alg1-prob-3-100|100|100|100|100-lllll-5_4.json"
##  [25] "alg1-prob-3-100|100|100|100|100-lllll-5_5.json"
##  [26] "alg1-prob-3-200|200|200|200|200-lllll-5_1.json"
##  [27] "alg1-prob-3-200|200|200|200|200-lllll-5_2.json"
##  [28] "alg1-prob-3-200|200|200|200|200-lllll-5_3.json"
##  [29] "alg1-prob-3-200|200|200|200|200-lllll-5_4.json"
##  [30] "alg1-prob-3-200|200|200|200|200-lllll-5_5.json"
##  [31] "alg1-prob-3-300|300|300|300|300-lllll-5_1.json"
##  [32] "alg1-prob-3-300|300|300|300|300-lllll-5_2.json"
##  [33] "alg1-prob-3-300|300|300|300|300-lllll-5_3.json"
##  [34] "alg1-prob-3-300|300|300|300|300-lllll-5_4.json"
##  [35] "alg1-prob-3-300|300|300|300|300-lllll-5_5.json"
##  [36] "alg1-prob-3-50|50|50|50|50-lllll-5_1.json"     
##  [37] "alg1-prob-3-50|50|50|50|50-lllll-5_2.json"     
##  [38] "alg1-prob-3-50|50|50|50|50-lllll-5_3.json"     
##  [39] "alg1-prob-3-50|50|50|50|50-lllll-5_4.json"     
##  [40] "alg1-prob-3-50|50|50|50|50-lllll-5_5.json"     
##  [41] "alg1-prob-4-100|100|100|100|100-lllll-5_1.json"
##  [42] "alg1-prob-4-100|100|100|100|100-lllll-5_2.json"
##  [43] "alg1-prob-4-100|100|100|100|100-lllll-5_3.json"
##  [44] "alg1-prob-4-100|100|100|100|100-lllll-5_4.json"
##  [45] "alg1-prob-4-100|100|100|100|100-lllll-5_5.json"
##  [46] "alg1-prob-4-200|200|200|200|200-lllll-5_1.json"
##  [47] "alg1-prob-4-200|200|200|200|200-lllll-5_2.json"
##  [48] "alg1-prob-4-200|200|200|200|200-lllll-5_3.json"
##  [49] "alg1-prob-4-200|200|200|200|200-lllll-5_4.json"
##  [50] "alg1-prob-4-200|200|200|200|200-lllll-5_5.json"
##  [51] "alg1-prob-4-300|300|300|300|300-lllll-5_1.json"
##  [52] "alg1-prob-4-300|300|300|300|300-lllll-5_2.json"
##  [53] "alg1-prob-4-300|300|300|300|300-lllll-5_3.json"
##  [54] "alg1-prob-4-300|300|300|300|300-lllll-5_4.json"
##  [55] "alg1-prob-4-300|300|300|300|300-lllll-5_5.json"
##  [56] "alg1-prob-4-300|300|300|300|300-mmmmm-5_1.json"
##  [57] "alg1-prob-4-300|300|300|300|300-mmmmm-5_2.json"
##  [58] "alg1-prob-4-300|300|300|300|300-mmmmm-5_3.json"
##  [59] "alg1-prob-4-300|300|300|300|300-mmmmm-5_4.json"
##  [60] "alg1-prob-4-300|300|300|300|300-mmmmm-5_5.json"
##  [61] "alg1-prob-4-300|300|300|300|300-uuull-5_2.json"
##  [62] "alg1-prob-4-300|300|300|300|300-uuull-5_3.json"
##  [63] "alg1-prob-4-300|300|300|300|300-uuull-5_4.json"
##  [64] "alg1-prob-4-300|300|300|300|300-uuull-5_5.json"
##  [65] "alg1-prob-4-300|300|300|300|300-uuuuu-5_2.json"
##  [66] "alg1-prob-4-300|300|300|300|300-uuuuu-5_3.json"
##  [67] "alg1-prob-4-300|300|300|300|300-uuuuu-5_4.json"
##  [68] "alg1-prob-4-300|300|300|300|300-uuuuu-5_5.json"
##  [69] "alg1-prob-4-50|50|50|50|50-lllll-5_1.json"     
##  [70] "alg1-prob-4-50|50|50|50|50-lllll-5_2.json"     
##  [71] "alg1-prob-4-50|50|50|50|50-lllll-5_3.json"     
##  [72] "alg1-prob-4-50|50|50|50|50-lllll-5_4.json"     
##  [73] "alg1-prob-4-50|50|50|50|50-lllll-5_5.json"     
##  [74] "alg1-prob-5-100|100|100|100|100-lllll-5_1.json"
##  [75] "alg1-prob-5-100|100|100|100|100-lllll-5_2.json"
##  [76] "alg1-prob-5-100|100|100|100|100-lllll-5_3.json"
##  [77] "alg1-prob-5-100|100|100|100|100-lllll-5_4.json"
##  [78] "alg1-prob-5-100|100|100|100|100-lllll-5_5.json"
##  [79] "alg1-prob-5-100|100|100|100|100-uuull-5_1.json"
##  [80] "alg1-prob-5-100|100|100|100|100-uuull-5_2.json"
##  [81] "alg1-prob-5-100|100|100|100|100-uuull-5_3.json"
##  [82] "alg1-prob-5-100|100|100|100|100-uuull-5_4.json"
##  [83] "alg1-prob-5-100|100|100|100|100-uuull-5_5.json"
##  [84] "alg1-prob-5-200|200|200|200|200-lllll-5_1.json"
##  [85] "alg1-prob-5-200|200|200|200|200-lllll-5_2.json"
##  [86] "alg1-prob-5-200|200|200|200|200-lllll-5_3.json"
##  [87] "alg1-prob-5-200|200|200|200|200-lllll-5_4.json"
##  [88] "alg1-prob-5-200|200|200|200|200-lllll-5_5.json"
##  [89] "alg1-prob-5-200|200|200|200|200-mmmmm-5_1.json"
##  [90] "alg1-prob-5-200|200|200|200|200-mmmmm-5_2.json"
##  [91] "alg1-prob-5-200|200|200|200|200-mmmmm-5_3.json"
##  [92] "alg1-prob-5-200|200|200|200|200-mmmmm-5_4.json"
##  [93] "alg1-prob-5-200|200|200|200|200-mmmmm-5_5.json"
##  [94] "alg1-prob-5-200|200|200|200|200-uuull-5_1.json"
##  [95] "alg1-prob-5-200|200|200|200|200-uuull-5_2.json"
##  [96] "alg1-prob-5-200|200|200|200|200-uuull-5_3.json"
##  [97] "alg1-prob-5-200|200|200|200|200-uuull-5_4.json"
##  [98] "alg1-prob-5-200|200|200|200|200-uuull-5_5.json"
##  [99] "alg1-prob-5-200|200|200|200|200-uuuuu-5_1.json"
## [100] "alg1-prob-5-200|200|200|200|200-uuuuu-5_2.json"
## [101] "alg1-prob-5-200|200|200|200|200-uuuuu-5_3.json"
## [102] "alg1-prob-5-200|200|200|200|200-uuuuu-5_4.json"
## [103] "alg1-prob-5-200|200|200|200|200-uuuuu-5_5.json"
## [104] "alg1-prob-5-300|300|300|300-llll-4_1.json"     
## [105] "alg1-prob-5-300|300|300|300-llll-4_2.json"     
## [106] "alg1-prob-5-300|300|300|300-llll-4_3.json"     
## [107] "alg1-prob-5-300|300|300|300-llll-4_4.json"     
## [108] "alg1-prob-5-300|300|300|300-llll-4_5.json"     
## [109] "alg1-prob-5-300|300|300|300|300-lllll-5_1.json"
## [110] "alg1-prob-5-300|300|300|300|300-lllll-5_2.json"
## [111] "alg1-prob-5-300|300|300|300|300-lllll-5_3.json"
## [112] "alg1-prob-5-300|300|300|300|300-lllll-5_4.json"
## [113] "alg1-prob-5-300|300|300|300|300-lllll-5_5.json"
## [114] "alg1-prob-5-300|300|300|300|300-mmmmm-5_1.json"
## [115] "alg1-prob-5-300|300|300|300|300-mmmmm-5_2.json"
## [116] "alg1-prob-5-300|300|300|300|300-mmmmm-5_3.json"
## [117] "alg1-prob-5-300|300|300|300|300-mmmmm-5_4.json"
## [118] "alg1-prob-5-300|300|300|300|300-mmmmm-5_5.json"
## [119] "alg1-prob-5-300|300|300|300|300-uuull-5_1.json"
## [120] "alg1-prob-5-300|300|300|300|300-uuull-5_2.json"
## [121] "alg1-prob-5-300|300|300|300|300-uuull-5_3.json"
## [122] "alg1-prob-5-300|300|300|300|300-uuull-5_4.json"
## [123] "alg1-prob-5-300|300|300|300|300-uuull-5_5.json"
## [124] "alg1-prob-5-300|300|300|300|300-uuuuu-5_1.json"
## [125] "alg1-prob-5-300|300|300|300|300-uuuuu-5_2.json"
## [126] "alg1-prob-5-300|300|300|300|300-uuuuu-5_3.json"
## [127] "alg1-prob-5-300|300|300|300|300-uuuuu-5_4.json"
## [128] "alg1-prob-5-300|300|300|300|300-uuuuu-5_5.json"
## [129] "alg1-prob-5-50|50|50|50|50-lllll-5_1.json"     
## [130] "alg1-prob-5-50|50|50|50|50-lllll-5_2.json"     
## [131] "alg1-prob-5-50|50|50|50|50-lllll-5_3.json"     
## [132] "alg1-prob-5-50|50|50|50|50-lllll-5_4.json"     
## [133] "alg1-prob-5-50|50|50|50|50-lllll-5_5.json"     
## [134] "alg1-prob-5-50|50|50|50|50-uuull-5_1.json"     
## [135] "alg1-prob-5-50|50|50|50|50-uuull-5_2.json"     
## [136] "alg1-prob-5-50|50|50|50|50-uuull-5_3.json"     
## [137] "alg1-prob-5-50|50|50|50|50-uuull-5_4.json"     
## [138] "alg1-prob-5-50|50|50|50|50-uuull-5_5.json"

1140/1142 problems have 5 instances solved for each configuration. Configurations with lees that 5 solved:

## # A tibble: 28 × 5
## # Groups:   p, m, method [11]
##        p     m method spAveCard solved
##    <dbl> <dbl> <chr>      <dbl>  <int>
##  1     2     5 l             50      0
##  2     2     5 l            100      0
##  3     2     5 l            200      0
##  4     2     5 l            300      0
##  5     3     5 l             50      0
##  6     3     5 l            100      0
##  7     3     5 l            200      0
##  8     3     5 l            300      0
##  9     4     5 l             50      0
## 10     4     5 l            100      0
## 11     4     5 l            200      0
## 12     4     5 l            300      0
## 13     4     5 m            300      0
## 14     4     5 u            300      1
## 15     4     5 ul           300      1
## 16     5     4 l            300      0
## 17     5     5 l             50      0
## 18     5     5 l            100      0
## 19     5     5 l            200      0
## 20     5     5 l            300      0
## 21     5     5 m            200      0
## 22     5     5 m            300      0
## 23     5     5 u            200      0
## 24     5     5 u            300      0
## 25     5     5 ul            50      0
## 26     5     5 ul           100      0
## 27     5     5 ul           200      0
## 28     5     5 ul           300      0

34/1142 have not been classified at all:

##  [1] "alg1-prob-4-200|200|200|200|200-mmmmm-5_1.json"
##  [2] "alg1-prob-4-200|200|200|200|200-mmmmm-5_2.json"
##  [3] "alg1-prob-4-200|200|200|200|200-mmmmm-5_3.json"
##  [4] "alg1-prob-5-100|100-uu-2_2.json"               
##  [5] "alg1-prob-5-100|100-uu-2_3.json"               
##  [6] "alg1-prob-5-100|100|100|100|100-mmmmm-5_5.json"
##  [7] "alg1-prob-5-100|100|100|100|100-uuuuu-5_1.json"
##  [8] "alg1-prob-5-100|100|100|100|100-uuuuu-5_4.json"
##  [9] "alg1-prob-5-100|100|100|100|100-uuuuu-5_5.json"
## [10] "alg1-prob-5-200|200|200|200-llll-4_1.json"     
## [11] "alg1-prob-5-200|200|200|200-llll-4_2.json"     
## [12] "alg1-prob-5-200|200|200|200-llll-4_3.json"     
## [13] "alg1-prob-5-200|200|200|200-llll-4_4.json"     
## [14] "alg1-prob-5-200|200|200|200-llll-4_5.json"     
## [15] "alg1-prob-5-200|200|200|200-mmmm-4_1.json"     
## [16] "alg1-prob-5-200|200|200|200-mmmm-4_2.json"     
## [17] "alg1-prob-5-200|200|200|200-mmmm-4_3.json"     
## [18] "alg1-prob-5-200|200|200|200-mmmm-4_4.json"     
## [19] "alg1-prob-5-200|200|200|200-mmmm-4_5.json"     
## [20] "alg1-prob-5-200|200|200|200-uull-4_1.json"     
## [21] "alg1-prob-5-200|200|200|200-uull-4_2.json"     
## [22] "alg1-prob-5-200|200|200|200-uull-4_3.json"     
## [23] "alg1-prob-5-200|200|200|200-uull-4_4.json"     
## [24] "alg1-prob-5-200|200|200|200-uull-4_5.json"     
## [25] "alg1-prob-5-300|300|300|300-mmmm-4_1.json"     
## [26] "alg1-prob-5-300|300|300|300-mmmm-4_2.json"     
## [27] "alg1-prob-5-300|300|300|300-mmmm-4_3.json"     
## [28] "alg1-prob-5-300|300|300|300-mmmm-4_4.json"     
## [29] "alg1-prob-5-300|300|300|300-mmmm-4_5.json"     
## [30] "alg1-prob-5-300|300|300|300-uull-4_1.json"     
## [31] "alg1-prob-5-300|300|300|300-uull-4_2.json"     
## [32] "alg1-prob-5-300|300|300|300-uull-4_3.json"     
## [33] "alg1-prob-5-300|300|300|300-uull-4_4.json"     
## [34] "alg1-prob-5-300|300|300|300-uull-4_5.json"

409/1108 classified files have not been fully classified (only classified extreme).

Problems solved for the analysis

Note that the width of objective \(i = 1, \ldots p\), \(w_i = [l_i, u_i]\) should be approx. \(10000m\). Check:

## # A tibble: 4 × 6
##       m mean_width1 mean_width2 mean_width3 mean_width4 mean_width5
##   <dbl>       <dbl>       <dbl>       <dbl>       <dbl>       <dbl>
## 1     2      19245.      19221.      19213.      18996.      18690.
## 2     3      28760.      28800.      28689.      28479.      27847.
## 3     4      38300.      38353.      38153.      37744.      36642.
## 4     5      47715.      47966.      47953.      47039.      44537.

Size of \(Y_N\)

What is \(|Y_N|\) given the different methods of generating the set of nondominated points for the subproblems?

## # A tibble: 4 × 3
##   method mean_card     n
##   <chr>      <dbl> <int>
## 1 l        325067.   235
## 2 m        419864.   305
## 3 u        102271.   305
## 4 ul       184743.   295

Does \(p\) have an effect?

## # A tibble: 16 × 4
## # Groups:   method [4]
##    method     p mean_card     n
##    <chr>  <dbl>     <dbl> <int>
##  1 l          2     5829.    60
##  2 m          2     6828.    80
##  3 u          2     1164.    80
##  4 ul         2     2920.    80
##  5 l          3    61381.    60
##  6 m          3   180435.    80
##  7 u          3    12475.    80
##  8 ul         3    26863.    80
##  9 l          4   370968.    60
## 10 m          4   476291.    75
## 11 u          4    79341.    75
## 12 ul         4   185223.    75
## 13 l          5   910910     55
## 14 m          5  1105081.    70
## 15 u          5   345012.    70
## 16 ul         5   637081.    60

Does \(m\) have an effect?

## # A tibble: 15 × 4
## # Groups:   method [4]
##    method     m mean_card     n
##    <chr>  <dbl>     <dbl> <int>
##  1 l          2     8173.    80
##  2 m          2     5688.    80
##  3 u          2     4201.    80
##  4 ul         2     4923.    80
##  5 l          3   166384.    80
##  6 m          3    90077.    80
##  7 u          3    37283.    80
##  8 ul         3    90425.    80
##  9 l          4   832349.    75
## 10 m          4   874692.    80
## 11 u          4   190675.    80
## 12 ul         4   485509.    80
## 13 m          5   775723.    65
## 14 u          5   194151.    65
## 15 ul         5   146013.    55

Let us try to fit the results using function \(y=c_1 s^{(c_2p)} m^{c_3p}\) (different functions was tried and this gave the highest \(R^2\)) for each method.

## # A tibble: 4 × 15
##   method fit    tidied   r.squared adj.r.squared sigma statistic   p.value    df
##   <chr>  <list> <list>       <dbl>         <dbl> <dbl>     <dbl>     <dbl> <dbl>
## 1 l      <lm>   <tibble>     0.804         0.802 1.04       475. 8.75e- 83     2
## 2 m      <lm>   <tibble>     0.765         0.764 1.22       492. 1.01e- 95     2
## 3 ul     <lm>   <tibble>     0.900         0.900 0.742     1317. 7.10e-147     2
## 4 u      <lm>   <tibble>     0.947         0.947 0.519     2705. 1.62e-193     2
## # ℹ 6 more variables: logLik <dbl>, AIC <dbl>, BIC <dbl>, deviance <dbl>,
## #   df.residual <int>, nobs <int>

## # A tibble: 4 × 4
##   method    c1     c2    c3
##   <chr>  <dbl>  <dbl> <dbl>
## 1 l      102.  0.0810 1.15 
## 2 m      100.  0.0823 1.08 
## 3 ul      31.6 0.117  1.10 
## 4 u       24.5 0.134  0.946

Relative size of \(Y_N\)

Nondominated points classification

We classify the nondominated points into, extreme, supported non-extreme and unsupported.

## # A tibble: 1 × 3
##   minPctEx avePctExt maxPctEx
##      <dbl>     <dbl>    <dbl>
## 1 0.000461    0.0461    0.330

## # A tibble: 4 × 4
##   method minPctEx avePctExt maxPctEx
##   <chr>     <dbl>     <dbl>    <dbl>
## 1 l      0.00966     0.0893    0.302
## 2 ul     0.00639     0.0721    0.330
## 3 m      0.000461    0.0205    0.147
## 4 u      0.00196     0.0133    0.104

Plots used in the paper